As designers strive to improve the capabilities of new integrated circuits (ICs), developments in IC design have dramatically increased the power, speed, and capability of the IC. As the power, speed, and capability of ICs increase, the number of input/output (I/O) terminals that each IC is interconnected with has also increased.
Normally, ICs are placed inside a “package” before they can be installed on a Printed Circuit Board (PCB). As is generally known, IC Package Interconnect is the process of designing the electrically conductive traces between the terminals on the IC die and the pins on the package. Using Electronic Design Automatic (EDA) tools, the human designer takes logical net data from the IC die and physical footprint data from the package. The designer uses this data to plan and design the electrical traces within the package to connect the IC die to the package pins. Once these connections are made, a connection is made from the package pins to the PCB.
Until recently, most packages had only a few dozen or a few hundred pins. The routing required to connect IC to package was not particularly difficult or time consuming. Modern Ball Grid Array (BGA) packages now routinely have hundreds or thousands of die pins. Some have over ten thousand die pins. As well, higher speed signals impose more strict constraints on the actual connections used and their relation to each other. A task that previously took a few hours can now take days or even weeks. Thus, automated solutions have been sought.
Almost all package auto-routers are based on the assumption that they are trying to create a path, for each net, between a start point and an end point. A net is typically defined as a collection of pins that need to be electrically connected. A list of all or some of the nets in a layout is referred to as a net list. If both of the start and end points of a path are not already established, then the auto-router cannot be used. Thus, before invoking a router, the user must establish a mapping of these source/destination pairings, which leads to significant problems.
In a high pin count package, the establishment of source-destination pin pairings could involve establishing mappings between thousands of pins, with routing happening on dozens of substrate layers. This leads to a massive jumble of connection path marker lines (flight lines) which is very difficult for a user to understand and change. Additionally, there are multiple interacting physical, electrical, and signal integrity rules which must all be satisfied for a chosen solution to be usable. In a design with n die pins and m package pins, the solution space is O(n*m). Within the solution space, there may be only a single assignment solution which will satisfy all constraints on the system.
One previous approach to providing a solution involves a process of mapping pins to achieve a pattern which minimizes the crossing of flight lines, while also averaging the length of the net assignments across the entire selection set. An alternate approach utilizes the mapping of pins by first breaking each of the source and destination sets into a set of pins for each available routing layer. Each layer's set of pins is then assigned separately based on a division of the pins into quadrants, e.g., north, south, east, and west. Each side is sorted individually, with the pins being mapped, in order, from the middle of the side out to the edges, regardless of crossing flight lines.
The prior approaches share many of the same disadvantages. Their performance is based on an assumption of a clean design, without consideration of assignments to pins beyond that assumption. In addition, both solutions consider only very limited physical rules in the form of crossed flight lines, flight line length, and relative pin locations. They do not consider any route line spacing rules, electrical constraints, or signal integrity issues. Further, neither approach considers the hierarchical ordering of nets and neither is able to perform when there are multiple die components in the package, since each solution is designed for use in single-chip, radially-routed packages. Further, neither is able to handle power and ground nets, which have many pins and can be routed in many different patterns. Under all of these limitations, assignment of all source pins to destination pins may occur, but the assignment may not be routable and may require significant manual refinement.
Accordingly, what is needed is an interconnect routing solution capable of performing net assignment in IC package designs that optimizes source and destination element mappings. The present invention addresses such a need.